import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Leetcode77 {
    public static void main(String[] args) {
        System.out.println(combine(1, 1));
    }

    public static List<List<Integer>> combine(int n, int k) {
        if (k > n) {
            return new ArrayList<>();
        }

        if (n == 1) {
            return new ArrayList<>(Collections.singletonList(new ArrayList<>(Collections.singletonList(1))));
        }

        if (k == 1) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 1; i <= n; i++) {
                res.add(new ArrayList<>(Collections.singletonList(i)));
            }

            return res;
        }

        List<List<Integer>> r = combine(n - 1, k);

        List<List<Integer>> res = combine(n - 1, k - 1);

        for (List<Integer> re : res) {
            re.add(n);
        }

        res.addAll(r);

        return res;
    }
}
